public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {23,32,69,16,37,73};
        heapSort(arr);

        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public static void heapSort(int[] arr){

        //构造大顶堆
        for(int i = arr.length/2-1; i>=0;i--){
            buildHeap(arr,i,arr.length-1);
        }

        //排序
        //q去堆顶
        for(int j =arr.length-1;j>=0;j--){

            swap(arr,0,j);
            buildHeap(arr,0,j-1);
        }
    }

    public static void buildHeap(int[] arr,int l, int r){

        for(int k = l*2+1; k<=r;k =k*2+1){
            if(k+1 <= r && arr[k+1] >arr[k]){
                k++;
            }
            if(arr[k] > arr[l]){
                swap(arr,k,l);
                l=k;
            }
        }
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] =arr[j];
        arr[j] = temp;
    }
}
